package com.minigame.leetCode;

import java.util.Arrays;

public class Hanoi {

    public static void main(String[] args) {
        int[][][] link = run(3);
        for (int[][] status : link) {
            System.out.println(Arrays.deepToString(status));
        }
    }

    public static int[][][] run(int n) {
        int[][] a = init(n);
        int[] actions = solution(n);
        int[][][] link = new int[actions.length + 1][][];
        int i = 0;
        link[i++] = a;
        for (int actionCode : actions) {
            link[i++] = a = move(a, actionCode);
        }
        return link;
    }

    /**
     * 初始状态
     * @param n 层数
     * @return 三塔初始状态
     */
    public static int[][] init(int n) {
        int[][] a = new int[3][0];
        a[0] = new int[n];
        for (int i = 0; i < n; i++) {
            a[0][i] = n - i;
        }
        return a;
    }

    /**
     * 动态规划解法
     * 1 : A -> B
     * 2 : B -> C
     * 3 : A -> C
     * 4 : B -> A
     * 5 : C -> B
     * 6 : C -> A
     * @param n 层数
     */
    public static int[] solution(int n) {
        int[][][] a = new int[n + 1][6][];
        a[0] = new int[6][0];
        for (int i = 1; i <= n; i++) {
            if (i < n - 1) {
                a[i][3] = concat(a[i - 1][1], 4, a[i - 1][5]);
                a[i][4] = concat(a[i - 1][5], 5, a[i - 1][0]);
                a[i][5] = concat(a[i - 1][4], 6, a[i - 1][3]);
            }
            if (i < n) {
                a[i][0] = concat(a[i - 1][2], 1, a[i - 1][4]);
                a[i][1] = concat(a[i - 1][3], 2, a[i - 1][2]);
            }
            a[i][2] = concat(a[i - 1][0], 3, a[i - 1][1]);
        }
        return a[n][2];
    }

    /**
     * 拼接形成新数组
     * @param a1 数组1
     * @param n 中间数
     * @param a2 数组2
     * @return 拼接后的数组
     */
    public static int[] concat(int[] a1, int n, int[] a2) {
        int[] a = new int[a1.length + 1 + a2.length];
        int i = 0;
        for (int j = 0; j < a1.length;) {
            a[i++] = a1[j++];
        }
        a[i++] = n;
        for (int j = 0; j < a2.length;) {
            a[i++] = a2[j++];
        }
        return a;
    }

    /**
     * 1 : A -> B
     * 2 : B -> C
     * 3 : A -> C
     * 4 : B -> A
     * 5 : C -> B
     * 6 : C -> A
     * @param a 塔状态
     * @param actionCode 移动动作代号
     */
    public static int[][] move(int[][] a, int actionCode) {
        int[][] status;
        switch (actionCode) {
            case 1:
                status = transfer(a[0], a[1]);
                return new int[][]{status[0], status[1], a[2]};
            case 2:
                status = transfer(a[1], a[2]);
                return new int[][]{a[0], status[0], status[1]};
            case 3:
                status = transfer(a[0], a[2]);
                return new int[][]{status[0], a[1], status[1]};
            case 4:
                status = transfer(a[1], a[0]);
                return new int[][]{status[1], status[0], a[2]};
            case 5:
                status = transfer(a[2], a[1]);
                return new int[][]{a[0], status[1], status[0]};
            case 6:
                status = transfer(a[2], a[0]);
                return new int[][]{status[1], a[1], status[0]};
        }
        return null;
    }

    /**
     * 从起始塔移动一块至目标塔
     * @param source 起始塔
     * @param target 目标塔
     * @return 移动后变化的两塔状态
     */
    public static int[][] transfer(int[] source, int[] target) {
        int[] to = Arrays.copyOf(target, target.length + 1);
        to[target.length] = source[source.length - 1];
        int[] from = Arrays.copyOf(source, source.length - 1);
        return new int[][]{from, to};
    }
}
